#ifndef __DOUBLELINKLIST_H_
#define __DOUBLELINKLIST_H_
#include <iostream>
#include <exception>

template<typename T>
class DoubleLinkList
{
public:
    DoubleLinkList();

    void InsertTail(const T& element);

    void RemoveByIndex(int index);

    T& GetHead()
    {
        if(size == 0)
            throw std::out_of_range("链表为空");
        return head->next->data;
    }

    T& GetTail()
    {
        if(size == 0)
            throw std::out_of_range("链表为空");
        return tail->data;
        tail = tail->prev;
    }

    int Size(){return size;}

    void UpDateByElement(const T &Oldelement,const T &Newelement);

    void InsertHead(const T& element);

    void InsertByIndex(int index,const T& element);

    void RemoveByElement(const T& element);

    T& operator[](int index);

    size_t FindByElement(const T& element);

    DoubleLinkList Merge(const DoubleLinkList & list)
    {
        DoubleLinkList result;
        Node *p1 = tail;
        Node *p2 = list.tail;
        while(p1->prev != head && p2->prev != head)
        {
            if(p1->value < p2->value)
            {
                result.InsertTail(p2->value);
                p2 = p2->prev;
            }
            else if(p1->value > p2->value)
            {
                result.InsertTail(p1->value);
                p1 = p1->prev;
            }
            else
            {
                result.InsertTail(p2->value);
                result.InsertTail(p1->value);
                p2 = p2->prev;
                p1 = p1->prev;
            }
        }
        while(p1 && p1->prev != nullptr)
        {
            result.InsertTail(p1->value);
            p1 = p1->prev;
        }
        while(p2 && p2->prev != nullptr)
        {
            result.InsertTail(p2->value);
            p2 = p2->prev;
        }
        return result;
    }

    void Sort()
    {
        FastSort(head->next,tail);
    }

    void show()
    {
        std::cout<<"size : "<<size<<std::endl;
        Node *travelPoint = head->next; //存放有效数据的第一个节点
        while(travelPoint != nullptr) //当前节点存在
        {
            std::cout<<travelPoint->value<<" "; //当前指针不为空
            travelPoint = travelPoint->next; //访问下一个节点
        }
        std::cout<<std::endl;
    }

    void ReserveShow() //反向show
    {
        std::cout<<"size : "<<size<<std::endl;
        Node *travelPoint = tail; 
        while(travelPoint != head) //排除头节点
        {
            std::cout<<travelPoint->value<<" "; 
            travelPoint = travelPoint->prev; 
        }
        std::cout<<std::endl;
    }

    template<typename U>
    friend std::ostream& operator<<(std::ostream &os,const DoubleLinkList<U>& list);
private:
    struct Node
    {
        Node(const T& element)
        {
            next = prev = nullptr;
            data = element;
        }
        T data;
        Node * next;
        Node * prev;
    };

    void FastSort(Node *head,Node *tail)
    {
        if(head <= tail )
        {
            return;
        }
        int temp  = head->next->value; 
        Node *start = head->next;
        Node *end = tail;
        while(start != end)
        {
            while(end->value > temp && start != end)
            {
                end = end->prev;
            }
            if(start != end)
            {
                start->next->value = end->value;
            }
            while(start->value < temp && start != end)
            {
                start = start->next;
            }
            if(start != end)
            {
                end->prev->value = start->next->value; 
            }
        }
        start->value = temp;
        FastSort(head->prev,start);
        FastSort(end->next,tail);
    }

    Node * tail;
    Node * head;
    int size;
};

template<typename T>
DoubleLinkList<T>::DoubleLinkList():size(0)
{
    head = tail = new Node(T()); // 匿名对象T()
}

template <typename T>
inline void DoubleLinkList<T>::InsertTail(const T &element)
{
    Node *newNode = new Node(element);
    tail->next = newNode;
    newNode->prev = tail;
    tail = newNode;
    size++;
}

template <typename T>
inline std::ostream& operator<<(std::ostream &os, const DoubleLinkList<T> &list)
{   
    //typename声明后面跟随的模板是一个类型
    typename DoubleLinkList<T>:: Node *travelPoint = list.head->next; 
    while(travelPoint != nullptr) 
    {
        std::cout<<travelPoint->data<<" "; 
        travelPoint = travelPoint->next;
    }
    std::cout<<std::endl;
    return os;
}

template <typename T>
void DoubleLinkList<T>::RemoveByIndex(int index)
{
    if(index < 0 || index >= size)
    {
        return;
    }
    Node *travelPoint = head;
    for(int i = 0; i < index; i++)
    {
        travelPoint = travelPoint->next;
    }
    Node *freeNode = travelPoint->next;
    travelPoint->next = freeNode->next;
    if(freeNode == tail)
    {
        tail = tail->prev;
    }
    else
    {
        freeNode->next->prev = travelPoint;
    }
    delete freeNode;
    size--;
}

template <typename T>
void DoubleLinkList<T>::UpDateByElement(const T &Oldelement,const T &Newelement)
{
    Node * travelPoint = head->next;
    while(travelPoint != nullptr)
    {
        if(travelPoint->value == Oldelement)
        {
            travelPoint->value = Newelement;
        }
        travelPoint = travelPoint->next;
    }
}

template <typename T>
inline void DoubleLinkList<T>::InsertHead(const T &element)
{
    Node *newNode = new Node(element);
    newNode->next = head->next;
    newNode->prev = head;
    head->next = newNode;
    if(size != 0)
    {
        newNode->next->prev = newNode;
    }
    else
    {
        tail = newNode;
    }
    size++;
}

template <typename T>
inline void DoubleLinkList<T>::InsertByIndex(int index, const T &element)
{
    if(index < 0 || index > size)
    {
        return;
    }
    Node *travelPoint = head;
    for(int i = 0; i < index; i++) 
    {
        travelPoint = travelPoint->next;
    }

    Node *newNode = new Node(element);
    newNode->next = travelPoint->next;
    newNode->prev = travelPoint;
    travelPoint->next = newNode;
    if (newNode->next != nullptr)
    {
        newNode->next->prev = newNode;
    }
    else
        tail = newNode;
    size++;
}

template <typename T>
inline void DoubleLinkList<T>::RemoveByElement(const T &element)
{
    Node *travelPoint = head;
    while(travelPoint->next != nullptr)
    {
        if(travelPoint->next->value == element)
        {
            Node *freeNode = travelPoint->next;
            travelPoint->next = freeNode->next;
            if(freeNode == tail)
            {
                tail = tail->prev;
            }
            else
            {
                freeNode->next->prev = travelPoint;
            }
            delete freeNode;
            size--;
        }
        else 
        {
            travelPoint = travelPoint->next;
        }
    }
}
template <typename T>
T& DoubleLinkList<T>::operator[](int index)
{
    Node *travelPoint = head;
    for(int i = 0;i <= index; i++)
    {
        travelPoint = travelPoint->next;
    }
    return travelPoint->value;
}

template <typename T>
inline size_t DoubleLinkList<T>::FindByElement(const T &element)
{
    size_t result = 0;
    Node * travelPoint = head->next;
    while(travelPoint != nullptr)
    {
        if(travelPoint->value != element)
        {
            travelPoint = travelPoint->next;
            result++;
        }
        else
            break;
    }
    return result;
}



#endif


